import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return string字符串ArrayList
     */
    public ArrayList<String> generateParenthesis (int n) {
        // write code here
        ArrayList<String> res=new ArrayList<String>();
        StringBuffer str=new StringBuffer();
        dfs(res,str,0,0,n);
        return res;
    }
    public  void dfs(ArrayList<String> res,StringBuffer str,int left,int right,int n){
if(right==n){
    res.add(new String(str));
    return;
}
if(left<n){
    str.append('(');
    dfs(res,str,left+1,right,n);
    str.deleteCharAt(str.length()-1);
}
if(right<left){
    str.append(')');
    dfs(res,str,left,right+1,n);
    str.deleteCharAt(str.length()-1);
}
    }
}